I. Field of the Invention
The present invention relates to compressing incoming data by arithmetic coding encoding and retrieving the original data by arithmetic coding decoding.
II. Description of the Problem
In order to achieve a desired rate of data transfer or to store data in a limited memory space, it is often necessary or desirable to compress data into fewer bits. Some time after the data is compressed, the original data is to be retrieved--the latter step being referred to as de-compressing the data.
One application of data compression/de-compression involves optical imaging. In optical imaging, there are typically numerous pieces of information--such as darkness or shade of picture elements (pels)--which must be transferred at high rates or which must be stored for future use.
Arithmetic coding is one technique for achieving data compression and de-compression. In arithmetic coding, one decision after another is encoded to define successively smaller, lesser-included intervals along a number line. Arithmetic coding is described in various articles written by the present inventors: "An Introduction to Arithmetic Coding", by G. G. Langdon, Jr. IBM Journal of Research and Development, vol. 28, n. 2, March 1984, 135-149; and "Arithmetic Compression Code Control Parameters Approximation" (by D. R. Helman, G. G. Langdon, Jr., and J. J. Rissanen), in volume 23, No. 11, April 1981, pp. 5112-5114. The cited references are incorporated herein by reference to provide background.
As noted in the above articles, arithmetic coding provides that each decision has a plurality of possible exclusive outcomes (or events). Each outcome or event is represented in data by a symbol. In the optical imaging environment, for example, each decision may correspond to whether or not a given pel is black--the decision outcome being represented by a Y (or YES) symbol if the pel is black or an N (or NO) symbol if the pel is not black. A plurality of decisions may then be represented by a sequence of symbols, e.g. YNYYN . . .
In accordance with prior arithmetic coding teachings, a probability line has a current interval defined therealong. The first current interval is 0 to 1. The current interval is divided into segments in which each segment corresponds to one possible outcome for the next decision. Where there are only two possible outcomes for each decision, the current interval is divided into two segments. The length of each segment is based on its respective associated probability. The respective probabilities may remain fixed or may adapt as decision data is entered.
It is the correlating of larger segments to symbols which occur with greater frequency which leads to the compression effect. In the former cited article ("An Introduction to Arithmetic Encoding"), a 4-symbol arithmetic coding example is set forth in which each decision can result in an "a" event (having a 50% probability), a "b" event (having a 25% probability), a "c" event (having a 12.5% probability), or a "d" event (having a 12.5% probability). Representing the four events in binary form would require two bits for each decision where the events would be represented respectively by 00, 01, 10, and 11. For three decisions, such as aab which is highly likely, the straightforward uncoded data would be 00 00 01; requiring six bits. However, as observed in the article at page 137, the arithmetic coding approach permits the sequence aab to be represented by the value 0.001. Instead of six bits, the information can be represented in three bits. This conservation of bits results as successive events having relatively high associated probabilities occur.
The conservation deteriorates if numerous events occur for which there are low probabilities and relatively short line segments. With the above-noted probabilities, a sequence of events dd would be represented with uncoded data as 11 11 whereas, by arithmetic coding, the dd events would be represented by 111111. Provided that the larger segments in fact correspond to events which occur with correspondingly greater frequency, the additional bits needed for less probable symbols are outweighed by the conservation achieved when more probable symbols occur.
Hence, it is important to ensure that the associated probability (and segment length corresponding thereto) reasonably track the actual probabilities of the respective events.
Various techniques have been proposed for estimating event probabilities as more decision data history is gathered. In an article entitled "Method for Converting Counts to Coding Parameters" (by G. G. Langdon, Jr. and J. J. Rissanen), IBM Technical Disclosure Bulletin in volume 22, No. 7, December 1979, pp. 2880-2882, counters are used to detect changes in the symbol probabilities from observed symbol occurrences, and to modify the probability q of a less probable symbol (LPS). In particular, q is changed to reflect the number of counts of one symbol divided by the total number of symbols counted during a symbol string. That is, if k is the counts for one symbol and n is the number of counts for both symbols, symbol probability is changed based on k/n.
Another article by Langdon and Rissanen, "Compression of Black-White Images with Arithmetic Coding", IEEE Transactions on Communications, volume COM-29, No. 6, pp. 858-867, June 1981, also discusses adapting probabilities in an arithmetic coding environment. In discussing adaptation to nonstationary statistics, the IEEE article proceeds on page 865 as follows: "Suppose that we have received r [consecutive] 0's at state z, and our current estimate of the probability of [symbol] s(i) being 0 is p=c0/c [where c0 is a count defined as c(0.vertline.z,s(0) . . . s(t)) and c is a count defined as c(z,s(0) . . . s(t))]. We receive the symbol s(i). If s(i) is 0, we test: Is p'(r+1).gtoreq.0.2? If yes, we regard the observation as being . . . consistent with our estimate of p, and we update c0 and c by 1 to form a new estimate . . . If, however, p'(r+ 1)&lt;0.2, the observation is likely an indication of changed statistics, and we ought to be prepared to change our estimates to a larger value of p. We do this by halving the counts c0 and c before updating them by 1. If the received symbol s(i) is 1, we do the same confidence test using the probability p(r) . . . In reality, for the sake of easier implementation, we put suitable upper and lower bounds on the count of the less probable symbol for each skew value Q [Q(s)] to indicate when to halve or not the counts." In describing the Q(s) value, it is noted that the IEEE article discusses the approximating of the less probable symbol probability to the nearest value of 2.sup.-Q(s) where Q(s) is an integer referred to as the "skew number".
A particular approach to probability adaptation is included in a co-pending patent application entitled "Probability Adaptation for Arithmetic Coders", invented by W. B. Pennebaker and J. L. Mitchell, U.S. Ser. No. 06/805,163, filed on Dec. 4, 1985 which is incorporated herein by reference. Another probability estimator is also set forth in a patent of G. Goertzel and J. L. Mitchell entitled "Symmetrical Adaptive Data Compression/Decompression System", U.S. Pat. No. 4,633,490.
A general novel approach to adapting a probability estimator is also set forth in a co-pending application of W. B. Pennebaker and J. L. Mitchell filed on even date herewith and entitled "Probability Estimation Based on Decision History". which is incorporated herein by reference to the extent required to set forth the environment of the present invention. In the co-pending application, a plurality of possible probability values Qe for an event are prescribed--as in a table. Based on the invention disclosed in the co-pending application, an augend value A is defined and, with each decision, the augend value is reduced. The amount by which the augend value is reduced is event dependent. That is, in a binary application in which each decision may result in a less probable symbol (LPS) having a current estimated probability Qe being entered or a more probable symbol (MPS) being entered, the entering of an LPS results in the augend value being reduced to the current Qe value; whereas the entering of an MPS results in the augend value A being computed as A-Qe. If the up-dated value of A is less than a pre-defined minimum AMIN (which is greater than highest value of Qe), the up-dated value is renormalized (preferably by doubling) until A again is at least AMIN. A fundamental concept of the invention in the co-pending application is that the value of Qe is up-dated each time A is renormalized. If renormalization follows an LPS event, the Qe value (representing the estimated probability of the LPS event) is increased. If renormalization follows an MPS event, the Qe value diminishes. By linking Qe changes to augend value renormalization, the time for Qe change is readily determined without the need for counters and, contrary to prior techniques, provides close tracking of actual Qe probability over the range of Qe values.
In addition, the novel approach in the co-pending application has recognized that, at certain values of Qe, the up-dating procedure could be trapped at certain "bad" values. By way of example, values which--when doubled one or more times-are equal or nearly equal to AMIN can result in the following troublesome sequence. A is set equal to Qe(bad) after an LPS event; the up-dated A is doubled (and redoubled as required) until A is no longer less than AMIN and a higher Qe value is selected; because the up-dated A is equal or nearly equal to AMIN, a single MPS event results in A falling below AMIN thereby requiring a renormalization and a reduction in the Qe value to Qe(bad); if the LPS probability is actually much greater than the estimated Qe value, an LPS event may likely occur again thereby returning Qe to the higher value; again a single MPS event will cause a renormalization and a movement of the Qe value back to the Qe(bad) value; and so on. According to the teachings of the co-pending application, the "trapping" problem is addressed by disallowing the "bad" values. A shortcoming of that solution, however, is that certain values which are "bad" from a "trapping" standpoint are good values from an overall efficiency standpoint.
In addition to adapting probabilities based on an up-dated decision history, the implementation of arithmetic coding involves other problematic issues--such as "carry propagation" and "borrow propagation". The "carry propagation" problem is noted with reference to a first type of arithmetic coding encoder which up-dates a code stream C with successive decision inputs in accordance with the following conventions: (1) if the symbol being encoded is an LPS, C remains the same in value and the current interval becomes A(new)=Qe, and (2) if the symbol being encoded is an MPS, C is up-dated to C+Qe and the current interval becomes A(new)=A(previous)-Qe. As the interval A becomes smaller and such smaller intervals are added to C, the precision of C (i.e., the length of the code stream) increases. The precision may extend without any fixed limit as long as decision data is entered for encoding. Because C can be of indeterminate length (and precision) but only limited memory is available for containing code stream information, there may be a problem if a carry occurs. In particular, if the code stream value is a sequence of several hundred 1's but only the most recent bits of C are contained in a shift register, a problem results if some A is to be added to C. The carry will not be able to propagate through the several hundred 1 bits because only the most recent bits are accessible. One solution to carry propagation is referred to as bit-stuffing and has been outlined in the literature. The bit-stuffing of the prior technology suggests the insertion of at least one carry-receiving bit after a prescribed number of 1 bits in a row.
In an arithmetic coding encoder set forth in a co-pending patent application filed on even date herewith, entitled "Arithmetic Coding Data Compression/De-compression By Selectively Employed, Diverse Arithmetic Encoders and Decoders," invented by J. L. Mitchell and W. B. Pennebaker, an "optimum" software encoder is described in which the code point remains fixed in value or decrements with each encoded decision. Accordingly, when the code stream C.sub.s includes a string of 0 bits and a subtraction is required, a borrow may propagate beyond the length of a shift register which contains the most recent portion of the code stream. Such "borrow propagation" is accounted for in the above-identified co-pending application by converting some or all Hex `00` bytes in the encoded code stream to Hex `FF` with a carry bit. In this way, the borrow propagation becomes a carry propagation situation. Accounting for carry and borrow without sacrificing coding efficiency and requiring numerous additional bits is a desired end.
As a further aspect of arithmetic encoding, it is desirable to enter control words in the code stream. That is, it is desirable to enable an external controller to break into the code stream and insert a control word. At the decoder end, another controller should be able to detect and strip the control word from the received string of data. With regard to control word insertion, it is desirable to (a) provide for a large number of possible control words and (b) identify the presence of a control word without substantially reducing coding efficiency. In the aforementioned patent application relating to arithmetic coding data compression/decompression, a thirty-two bit register is provided for containing portions of the code stream en route to a buffer. The least significant twelve bits (0 through 11) represents a "fractional" portion of the code stream which is aligned with the current value of A. Bit 12 corresponds to a spacer bit. Bits 13 through 20 represent an 8-bit byte of code stream data that is next to be shipped to the buffer. Bit 21 is a carry receiver bit. Of the two bits which precede bit 21, bit 22 is used for identifying whether a control word is inserted. Bits 31 through 24 provide a flag bit which shifts left as data bits enter at bit 0. (After eight shifts, the flag bit is at a bit position which indicates that a byte of data is ready to be shipped to the buffer.) With the single spacer bit, two stuffed bits may be required under certain conditions.